from collections import defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ans_left, ans_right = -1, len(s)  # 初始化结果为无效区间
        cnt = defaultdict(int)
        for c in t:
            cnt[c] += 1  # 统计 t 中字符的欠账次数
        less = len(cnt)  # 需要覆盖的字符种类数

        left = 0
        for right, c in enumerate(s):  # 移动右指针
            cnt[c] -= 1
            if cnt[c] == 0:  # 当前字符的欠账已还清
                less -= 1
            while less == 0:  # 窗口已覆盖 t
                if right - left < ans_right - ans_left:  # 更新最短子串
                    ans_left, ans_right = left, right
                # 尝试移动左指针
                x = s[left]
                if cnt[x] == 0:  # 移出 x 会导致欠账
                    less += 1
                cnt[x] += 1
                left += 1
        return "" if ans_left < 0 else s[ans_left: ans_right + 1]